import java.util.*;
public class Test {
    public static void main(String[] args) {
        String str = "0fd0a3525bcxv986";
        StringBuffer stringBuffer = new StringBuffer();


        for (int i = 0; i < 26; i++) {
           str = str.replace((char)('a' + i),' ');
            System.out.println(str);
        }
        String[] strs = str.split(" ");
    }

    /*
    题目2 ：不用库函数，求x的平方和，只要整数部分
     */
    //方法1： 二分查找
    //找到 k² <= x 中 k 的最大值！
    public int mySqrt(int x) {
        //这里要从0开始才对！
        int l = 0;
        int r = x;
        int ans = 0;
        while(l <= r){
            int mid = (l + r) / 2;
            if((long)mid * mid <= x){
                ans = mid;
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }
        return ans;
    }

    /*
    题目2 ： 数组中的重复数字
     */
    //在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。
    // 数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
    // 请找出数组中任意一个重复的数字。

    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while(i < nums.length){
            if(nums[i] == i){
                i++;
                continue;
            }
            if(nums[nums[i]] == nums[i]){
                return nums[i];
            }
            int temp = nums[i];
            nums[i] = nums[temp];
            nums[temp] = temp;
        }
        return -1;
    }

    /*
    题目3 ：有序数组的平方
     */
    //给你一个按 非递减顺序 排序的整数数组 nums
    // 返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
    //自己一拍脑门想出来的方法：
    //先依次平方，再排序！
    public int[] sortedSquares1(int[] nums) {
        for(int i = 0; i < nums.length; i++){
            nums[i] = nums[i] * nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }

    //双指针：
    //利用数组已经有序的条件，找到负数与非负数交界的下标 neg
    // 0 ~ neg 为负数，平方后为非递增子序列
    //neg + 1 ~ n - 1 为整数，平方后为非递减子序列
    //再将两部分 归并排序即可 ！
    //时间复杂度 O(n)
    //k空间复杂度 O(n)
    public int[] sortedSquares2(int[] nums) {
        int neg = 0;
        int n = nums.length;
        for(int i = 0; i < n; i++){
            if(nums[i] < 0){
                neg = i;
            }else{
                break;
            }
        }

        int[] ans = new int[n];
        int i = neg;
        int j = neg + 1;
        int index = 0;
        while(i >= 0 || j < n){
            if(i < 0){
                ans[index] = nums[j] * nums[j];
                j++;
            }else if(j == n){
                ans[index] = nums[i] * nums[i];
                i--;
            }else if(nums[i] * nums[i] < nums[j] * nums[j]){
                ans[index] = nums[i] * nums[i];
                i--;
            }else{
                ans[index] = nums[j] * nums[j];
                j++;
            }
            index++;
        }
        return ans;
    }

    //这个方法跟上一个双指针是异曲同工之妙！
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        for(int i = 0, j = n - 1, pos = n - 1; i <= j; ){
            if(nums[i] * nums[i] < nums[j] * nums[j]){
                ans[pos] = nums[j] * nums[j];
                j--;
            }else{
                ans[pos] = nums[i] * nums[i];
                i++;
            }
            pos--;
        }
        return ans;
    }

    /*
    题目 4：判断一个单链表是否为回文链表
     */
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    //时间复杂度 O(N)
    //空间复杂度 O(N)
    public boolean isPalindrome(ListNode head) {
        //因为不知道这个链表有多少个节点
        //所以不用数组，用list
        //这里为什么只能用 ArrayList
        //反而用 LinkedList 会超出时间限制！
        List<Integer> list = new ArrayList<>();
        ListNode cur = head;
        while(cur != null){
            list.add(cur.val);
            cur = cur.next;
        }
        int l = 0;
        int r = list.size() - 1;
        while(l < r){
            //val 的范围 0 ~ 9
            //这里可以不用 equals 也行
            if(list.get(l) != (list.get(r))  ){
                return false;
            }

            l++;
            r--;
        }
        return true;
    }

    // 有没有空间复杂度为 O（1）的解法
    //快慢指针！
    //方法1：用一个数组把链表值都记录下来
    public boolean isPalindrome1(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode cur = slow.next;
        ListNode curNext = null;
        //第一步 ：后半部分反转！
        while(cur != null){
            curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //此处slow指向链表的最后一个节点！
        //第二步：比较节点值是否回文
        cur = head;
        while(cur != slow){
            if(cur.val != slow.val){
                return false;
            }
            //偶数情况的退出循环的条件
            if(cur.next == slow){
                return true;
            }
            cur = cur.next;
            slow = slow.next;
        }
        return true;
    }


    /*
    题目 5：从尾到头打印链表
     */

    public int[] reversePrint(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while(cur != null){
            stack.push(cur);
            cur = cur.next;
        }

        int[] ans = new int[stack.size()];

        int i = 0;
        while(!stack.isEmpty()){
            ans[i] = stack.pop().val;
            i++;
        }
        return ans;
    }








}
